8.6 线性查找

线性查找是最基础的一种查找算法。其思想非常简单，就是从头到尾依次遍历整个数组或列表，逐个元素进行比较，直到找到目标元素为止。

由于其实现和理解非常直观，线性查找通常是学习查找算法的第一步。

本节代码存放目录为 lesson20

概念与原理

线性查找的原理如下：

• 从序列的第一个元素开始，与目标值进行比较。

• 如果当前元素与目标值相等，则查找成功，返回该元素的索引。

• 如果不相等，则继续比较下一个元素，直到找到目标值或者遍历完整个序列。

• 如果遍历完整个序列仍未找到目标值，则返回未找到。

线性查找的特点如下：

• 时间复杂度：最坏情况下，线性查找需要遍历整个数组，因此其时间复杂度为 O(n)。

• 适用场景：线性查找适用于任何类型的列表或数组，尤其是当数据量较小或数据未排序时。

• 稳定性：线性查找是稳定的查找算法。

线性查找的步骤示例

给定如下数组，目标是查找元素 4：

[5, 3, 8, 4, 2]

通过线性查找的步骤如下：

第一轮：

- 比较 arr[0] 与目标值 4，不相等，继续查找。

第二轮：

- 比较 arr[1] 与目标值 4，不相等，继续查找。

第三轮：

- 比较 arr[2] 与目标值 4，不相等，继续查找。

第四轮：

- 比较 arr[3] 与目标值 4，相等，查找成功，返回索引 3。

最终，目标值 4 位于索引 3，查找成功。

线性查找的时间复杂度

线性查找的时间复杂度取决于目标值在数组中的位置：

• 最坏情况：O(n)，即目标值位于数组末尾或不在数组中。

• 最好情况：O(1)，即目标值位于数组的第一个位置。

• 平均情况：O(n)，即目标值随机分布在数组中。

由于线性查找需要逐个比较元素，它的时间复杂度随着数组长度的增加而线性增长，因此在数据量较大时，线性查找的效率较低。

Go 语言的实现

实现代码如下：

// linearSearch 实现线性查找
func linearSearch(arr []int, target int) int {
    // 遍历数组
    for i, val := range arr {
        // 如果找到目标值，返回其索引
        if val == target {
            return i
        }
    }
    // 如果找不到，返回 -1
    return -1
}

func main() {
    arr := []int{5, 3, 8, 4, 2}
    target := 4

    // 执行线性查找
    result := linearSearch(arr, target)

    if result != -1 {
        fmt.Printf("元素 %d 找到，索引为: %d\n", target, result)
    } else {
        fmt.Println("元素未找到")
    }
}

执行结果如下所示：

元素 4 找到，索引为: 3

在上面的代码中，linearSearch 函数通过 for 循环遍历数组，如果找到目标值则返回其索引，否则返回 -1 表示未找到。

小结

本节我们讲解了线性查找的基本原理、步骤示例和 Go 语言的实现。

关于本节总结如下：

• 时间复杂度：线性查找的时间复杂度为 O(n)，适用于数据量较小的场景。

• 适用场景：线性查找适合无序数组，特别是在数据量较小或者不经常进行查找操作的情况下。

• 局限性：线性查找效率较低，不适用于大规模数据集。